package basic.study.algorithms.search;

public class Bsearch {

    public static void main(String[] args) {

    }

    public static int bsearch1(int[] arr, int value) {
        int low = arr[0];
        int high = arr[arr.length - 1];

        while(low <= high) {
            int middle = low + ((high - low)>>1);
            if( arr[middle] == value) {
                return middle;
            } else if(arr[middle] < value) {
                low = middle + 1;
            } else {
                high = middle - 1;
            }
        }
        return -1;
    }
    //bsearch2(arr, arr[0], arr[arr.length-1], int value)
    public static int bsearch2(int[] arr, int low, int high, int value) {
        if(low > high) return -1;

        int middle = low + ((high - low)>>1);
        if(arr[middle] == value) return middle;
        else if (arr[middle] < value) return bsearch2(arr, middle+1, high, value);
        else return bsearch2(arr, low, middle-1, value);
    }

    //查找第一个值等于给定值的元素
    public static int bsearch3(int[] arr, int n, int value) {
        int low = 0;
        int high = n - 1;
        while(low <= high) {
            int mid = low + ((high - low)>>1);
            if (arr[mid] > value) {
                high = mid - 1;
            } else if (arr[mid] < value) {
                low = mid + 1;
            } else {
                if((mid == 0)|| (arr[mid-1] != value)) return mid;
                else high = mid - 1;
            }
        }
        return -1;
    }

    //查找最后一个值等于给定值的元素
    public static int bsearch4(int[] arr, int n, int value) {
        int low = 0;
        int high = n - 1;
        while(low <= high) {
            int mid = low + ((high - low) >> 1);
            if (arr[mid] > value) {
                high = mid - 1;
            }else if(arr[mid] < value) {
                low = mid + 1;
            }else {
                if ((mid == n-1) || (arr[mid+1] != value)) return mid;
                else low = mid + 1;
            }
        }
        return -1;
    }

    //查找第一个大于等于给定值的元素
    public static int bsearch5(int[] a, int n, int value) {
        int low = 0;
        int high = n -1;
        while(low <= high) {
            int mid = low + ((high - low)>> 1);
            if(a[mid] < value) {
                low = mid + 1;
            }
            else if (a[mid] >= value){
                if ((mid == 0) || (a[mid-1] < value)) return mid;
                else high = mid - 1;
            }
        }
        return -1;
    }

    //查找最后一个小于等于给定值的元素
    public static int bsearch6(int[] a, int n, int value) {
        int low = 0;
        int high = n - 1;
        while(low <= high) {
            int mid = low + ((high - low )>> 1);
            if (a[mid] > value) {
                high = mid - 1;
            } else if(a[mid] <= value) {
                if ((mid == n-1) || (a[mid + 1] > value)) return mid;
                else low = mid + 1;
            }
        }
        return -1;
    }
}
